Comparison on uniformly increasing integer arrays with random targets.
Manual Big-O Analysis
linear_search
Static analysis of `linear_search`:
- Recursion: no
- Max loop nesting depth: 1
- Divide-and-conquer hints: no
**Estimated Time Complexity:** O(n)
**Estimated Space Complexity:** O(1)
Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space.
These are heuristics; empirical results below provide a practical check.
binary_search
Static analysis of `binary_search`:
- Recursion: no
- Max loop nesting depth: 1
- Divide-and-conquer hints: yes
**Estimated Time Complexity:** O(n)
**Estimated Space Complexity:** O(1)
Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space.
These are heuristics; empirical results below provide a practical check.
Beginner-friendly Summary
linear_search When the input size n doubles, the runtime grows by approximately 2.08×, which suggests performance closer to O(n).
binary_search When the input size n doubles, the runtime grows by approximately 1.09×, which suggests performance closer to O(log n).
Interview-style Summaries
- linear_search linear_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
- binary_search binary_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
Runtime Benchmarks
Table (mean ± 95% CI)
| n |
linear_search |
binary_search |
| 1000 |
15.46 µs ± 6.87 µs |
1.72 µs ± 130.18 ns |
| 2000 |
28.77 µs ± 11.52 µs |
1.84 µs ± 131.06 ns |
| 4000 |
56.89 µs ± 22.32 µs |
2.03 µs ± 218.72 ns |
| 8000 |
129.09 µs ± 64.29 µs |
2.17 µs ± 122.59 ns |
| 16000 |
196.70 µs ± 100.18 µs |
2.63 µs ± 409.94 ns |
| 32000 |
543.67 µs ± 181.70 µs |
2.59 µs ± 292.80 ns |
Peak Memory (per call)
Table (mean ± 95% CI)
| n |
linear_search |
binary_search |
| 1000 |
211.64 B ± 18.98 B |
170.91 B ± 7.61 B |
| 2000 |
226.91 B ± 11.34 B |
181.09 B ± 7.61 B |
| 4000 |
232.00 B ± 0.00 B |
196.36 B ± 8.79 B |
| 8000 |
232.00 B ± 0.00 B |
193.82 B ± 9.49 B |
| 16000 |
232.00 B ± 0.00 B |
201.45 B ± 5.67 B |
| 32000 |
232.00 B ± 0.00 B |
204.00 B ± 0.00 B |
Comparison Summary
Best/worst runtime per n (lower is better). Mean ranks aggregate performance across all n.
| n |
Best Runtime |
Worst Runtime |
Mean Ranks |
| 1000 |
binary_search |
linear_search |
linear_search: 2.00
binary_search: 1.00
|
| 2000 |
binary_search |
linear_search |
linear_search: 2.00
binary_search: 1.00
|
| 4000 |
binary_search |
linear_search |
linear_search: 2.00
binary_search: 1.00
|
| 8000 |
binary_search |
linear_search |
linear_search: 2.00
binary_search: 1.00
|
| 16000 |
binary_search |
linear_search |
linear_search: 2.00
binary_search: 1.00
|
| 32000 |
binary_search |
linear_search |
linear_search: 2.00
binary_search: 1.00
|
Methods
Methods:
- **Runtime** measured with `time.perf_counter()`; each (function, n) pair ran 11 times after 2 warmup iterations. GC was enabled and collected before runs.
- **Memory** peak measured with `tracemalloc` backend (`tracemalloc` by default).
- **Confidence Intervals:** T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed.
- **Reference curves** (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.